package _go

//思路 二分查找  一定要注边界

/*区间和中间数划分的配对关系：
划分 [left, mid] 与 [mid + 1, right] ，mid 被分到左边，对应 int mid = left + (right - left) / 2;；
划分 [left, mid - 1] 与 [mid, right] ，mid 被分到右边，对应 int mid = left + (right - left + 1) / 2;。
*/
func searchInsert(nums []int, target int) int {
	l, r := 0, len(nums)

	for l < r {
		//中间值
		m := l + (r-l)/2
		if nums[m] == target {
			return m
		} else if nums[m] > target {
			r = m
		} else {
			l = m + 1
		}
	}
	return l
}
